package cn.itcast.algorithm.exercise;

import org.junit.Test;

import java.util.Stack;

/**
 * 该题目的考点是测试栈的后进先出的数据结构
 * peek 获取栈顶元素 但不删除
 * pop 弹出栈顶元素（删除）
 * push 压栈
 * 左右括号匹配时要点是：即将入栈元素和栈顶元素成对匹配，如果匹配，栈顶元素出栈pop，否则新元素入栈。当栈中元素为空时，表示匹配完毕，数据合法
 * https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=308&tqId=726&ru=/exam/oj&qru=/ta/algorithm-start/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D308
 * create by zhangtian105 on 2022/5/13
 */
public class ExerciseAB3 {
    @Test
    public void testExerciseAB3() {
        System.out.println(isValid("([)]")); ;
    }

    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        int length = s.length() ;
        if(s == null || s.equals("") || length == 1) {
            return false ;
        }

        if(length % 2 != 0) {
            return false ;
        }

        if (s.startsWith(")") || s.startsWith("]") || s.startsWith("}")) {
            return false ;
        }

        // ((、()、()[]{}、([])、([)]
        // 定义一个栈
        Stack<String> specialStrStack = new Stack<>() ;
        // 左符号([{   右符号}])
        String[] arrStr = s.split("") ;

        for (int i = 0; i < arrStr.length; i++) {
            String pushStr = arrStr[i] ;
            if (i == 0) {
                // 匹配出栈，不匹配进栈
                specialStrStack.push(pushStr) ;
            }else {
                if (!specialStrStack.empty()) {
                    // 取出栈中的元素
                    String stackS = specialStrStack.peek() ;

                    if (stackS.equals("(") && pushStr.equals(")")){
                        specialStrStack.pop();
                    }else if (stackS.equals("[") && pushStr.equals("]")){
                        specialStrStack.pop();
                    }else if (stackS.equals("{") && pushStr.equals("}")){
                        specialStrStack.pop();
                    }else {
                        specialStrStack.push(pushStr) ;
                    }
                }else {
                    specialStrStack.push(pushStr) ;
                }
            }
        }

        if (!specialStrStack.empty()) {
            return false ;
        }

        return true ;
    }
}
